<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 3, Exercise 47<BR>

<BR>

</H1>

<P ALIGN=LEFT>

The code is given below and in the files <code class=var>dblcirc.*</code>.

Rather than keep a pointer to the first element of the ordered list,

we keep a pointer to the last.  Because of this, the asymptotic

complexity of each function is the same as for the corresponding

function of the class <code class=var>Chain</code>.

</P>

<HR class = coderule>

<PRE class = code>

template&lt;class T&gt;

class DoubleCircular {

   friend DoubleCircularIterator&lt;T&gt;;

   public:

      DoubleCircular() {last = 0;}

      ~DoubleCircular();

      bool IsEmpty() const {return last == 0;}

      int Length() const; 

      bool Find(int k, T&amp; x) const; 

      int Search(const T&amp; x) const; 

      DoubleCircular&lt;T&gt;&amp; Delete(int k, T&amp; x); 

      DoubleCircular&lt;T&gt;&amp; Insert(int k, const T&amp; x);

      void Output(ostream&amp; out) const;

   private:

      DoubleNode&lt;T&gt; *last; // pointer to rightmost node

};



template&lt;class T&gt;

DoubleCircular&lt;T&gt;::~DoubleCircular()

{// DoubleCircular destructor. Delete all nodes.

   if (!last) return;         // list is empty



   // delete all nodes

   DoubleNode&lt;T&gt; *current = last-&gt;right,

                               // current node

                 *next;        // next node

   while (current != last) {

      next = current-&gt;right;

      delete current;

      current = next;

      }

   delete last;

}



template&lt;class T&gt;

int DoubleCircular&lt;T&gt;::Length() const

{// Return the number of elements in the list.

   if (!last) return 0;  // list is empty



   // count nodes

   DoubleNode&lt;T&gt; *current = last-&gt;right;

   int len = 0;

   while (current != last) {

     len++;

     current = current-&gt;right;

     }

   len++;  // for last node

   return len;

}



template&lt;class T&gt;

bool DoubleCircular&lt;T&gt;::Find(int k, T&amp; x) const

{// Set x to the k'th element in the list.

 // Return false if no k'th; return true otherwise.

   if (k &lt; 1 || !last) return false;



   DoubleNode&lt;T&gt; *current = last-&gt;right;

   int index = 1;  // index of current

   while (index &lt; k &amp;&amp; current != last) {

      // move to next node

      current = current-&gt;right;

      index++;

      }

   if (index == k) {x = current-&gt;data;

                    return true;}

   return false; // no k'th element

}



template&lt;class T&gt;

int DoubleCircular&lt;T&gt;::Search(const T&amp; x) const

{// Locate x.  Return position of x if found.

 // Return 0 if x not in the chain.

   if (!last) return 0;  // list is empty



   // examine nodes

   DoubleNode&lt;T&gt; *current = last-&gt;right;

   int index = 1;  // index of current

   while (current-&gt;data != x &amp;&amp; current != last) {

      // move to next node

      current = current-&gt;right;

      index++;

      }

   if (current-&gt;data == x) return index;

   return 0;

}



template&lt;class T&gt;

DoubleCircular&lt;T&gt;&amp; DoubleCircular&lt;T&gt;::Delete(int k, T&amp; x)

{// Set x to the k'th element and delete it.

 // Throw OutOfBounds exception if no k'th element.

   if (k &lt; 1 || !last)

      throw OutOfBounds(); // no k'th

   

   // p will eventually point to k'th node

   DoubleNode&lt;T&gt; *p = last-&gt;right;

   int index = 1;  // index of p



   // move p to k'th

   for (; index &lt; k &amp;&amp; p != last; index++)

      p = p-&gt;right;



   // make sure p is at the k'th element

   if (index != k) throw OutOfBounds(); // no k'th



   // remove p from list

   p-&gt;right-&gt;left = p-&gt;left;

   p-&gt;left-&gt;right = p-&gt;right;



   // save k'th element, update last, and free node p

   x = p-&gt;data;

   if (p == last)  // check if new list is empty

      if (k == 1)  // new list is empty

         last = 0;

      else // not empty

         last = last-&gt;left;

   delete p;



   return *this;

}



template&lt;class T&gt;

DoubleCircular&lt;T&gt;&amp; DoubleCircular&lt;T&gt;::Insert(int k, const T&amp; x)

{// Insert x after the k'th element.

 // Throw OutOfBounds exception if no k'th element.

 // Pass NoMem exception if inadequate space.

   if (k &lt; 0) throw OutOfBounds();



   if (k) {// locate k'th node

      if (!last) throw OutOfBounds();  // empty list



      // p will eventually point to k'th node

      DoubleNode&lt;T&gt; *p = last-&gt;right;

      int index = 1;

      for (; index &lt; k &amp;&amp; p != last;

             index++)  // move p to k'th

         p = p-&gt;right;

      if (index != k) throw OutOfBounds(); // no k'th



      // insert after p

      DoubleNode&lt;T&gt; *y = new DoubleNode&lt;T&gt;;

      y-&gt;data = x;

      y-&gt;right = p-&gt;right;

      y-&gt;right-&gt;left = y;

      p-&gt;right = y;

      y-&gt;left = p;

      if (p == last) last = y;

      }

   else {// insert as first element

         DoubleNode&lt;T&gt; *y = new DoubleNode&lt;T&gt;;

         y-&gt;data = x;

         if (last) {// insert into nonempty list

            y-&gt;right = last-&gt;right;

            y-&gt;right-&gt;left = y;

            last-&gt;right = y;

            y-&gt;left = last;

            }

         else {// insert into an empty list

               last = y;

               y-&gt;left = y;

               y-&gt;right = y;

               }

         }



   return *this;

}



template&lt;class T&gt;

void DoubleCircular&lt;T&gt;::Output(ostream&amp; out) const

{// Insert the chain elements into the stream out.

   if (!last) return;

   DoubleNode&lt;T&gt; *current;

   for (current = last-&gt;right; current != last;

                         current = current-&gt;right)

      out &lt;&lt; current-&gt;data &lt;&lt; "  ";

  // output last node

  out &lt;&lt; current-&gt;data &lt;&lt; "  ";

}



// overload &lt;&lt;

template &lt;class T&gt;

ostream&amp; operator&lt;&lt;(ostream&amp; out, const DoubleCircular&lt;T&gt;&amp; x)

   {x.Output(out); return out;}

<HR class = coderule>

</pre>







</FONT>

</BODY>

</HTML>

